\chapter{模式匹配}

\section{BF}

\subsection{BF（Brute Force）}

在一个字符串中查找另一个字符串的操作称为模式匹配。其中，被查找的字符串被称为文本串，需要查找的子串称为模式串。\\

查找子串的最简单的算法就是采用暴力匹配的方式。暴力匹配的基本思想就是逐个比较相应位置的字符。\\

假设文本串为S，模式串为P：

\begin{enumerate}
	\item 如果当前字符匹配成功（即S[i] == P[j]），则i++， j++，继续匹配下一个字符。

	\item 如果失配（即S[i] != P[j]），令i = i - j + 1，j = 0，相当于每次匹配失败时，i回溯，j被置为0。
\end{enumerate}

例如当文本串S = "BBC ABCDAB ABCDABCDABDE"，P = "ABCDABD"。\\

S[0]为B，P[0]为A，不匹配（情形2）。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}         & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			\textcolor{red}{B} & B          & C          &            & A          & B          & C          & D          & A          & B          &             & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			\textcolor{red}{A} & B          & C          & D          & A          & B          & D          &            &            &            &             &             &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

然后再判断S[1]和P[0]是否匹配，相当于模式串向右移动一位。S[1]与P[0]还是不匹配（情形2）。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1}         & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			B          & \textcolor{red}{B} & C          &            & A          & B          & C          & D          & A          & B          &             & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			           & \textcolor{red}{A} & B          & C          & D          & A          & B          & D          &            &            &             &             &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

然后再判断S[2]和P[0]是否匹配，模式串再向右移动一位。直到S[4]与P[0]匹配成功（情形1）。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}         & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			B          & B          & C          &            & \textcolor{red}{A} & B          & C          & D          & A          & B          &             & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			           &            &            &            & \textcolor{red}{A} & B          & C          & D          & A          & B          & D           &             &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

此时i = 5，j = 1，接下来判断S[5]与P[1]是否匹配。S[5]与P[1]匹配成功（情形1）。可得i = 6，j = 2。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}         & \textbf{5}         & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			B          & B          & C          &            & \textcolor{red}{A} & \textcolor{red}{B} & C          & D          & A          & B          &             & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			           &            &            &            & \textcolor{red}{A} & \textcolor{red}{B} & C          & D          & A          & B          & D           &             &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

直到S[10]为空格，P[6]为D，不匹配（情形2）。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}         & \textbf{5}         & \textbf{6}         & \textbf{7}         & \textbf{8}         & \textbf{9}         & \textbf{10}        & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			B          & B          & C          &            & \textcolor{red}{A} & \textcolor{red}{B} & \textcolor{red}{C} & \textcolor{red}{D} & \textcolor{red}{A} & \textcolor{red}{B} &                    & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			           &            &            &            & \textcolor{red}{A} & \textcolor{red}{B} & \textcolor{red}{C} & \textcolor{red}{D} & \textcolor{red}{A} & \textcolor{red}{B} & \textcolor{red}{D} &             &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

此时i = 5，j = 0，相当于判断S[5]跟P[0]是否匹配。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5}         & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} & \textbf{21} & \textbf{22} \\
			\hline
			B          & B          & C          &            & A          & \textcolor{red}{B} & C          & D          & A          & B          &             & A           & B           & C           & D           & A           & B           & C           & D           & A           & B           & D           & E           \\
			\hline
			           &            &            &            &            & \textcolor{red}{A} & B          & C          & D          & A          & B           & D           &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

至此可以看出，按照暴力匹配算法的思路。同理，直到找到匹配的字符串或文本串遍历结束退出。\\

BF暴力匹配在最坏情况下时间复杂度是$ O(mn) $。\\

\mybox{BF}

\begin{lstlisting}[language=Python]
def brute_force(s, p):
    i = 0
    j = 0

    while i < len(s) and j < len(p):
        if s[i] == p[j]:
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0
    
    if j == len(p):
        return i - j
    else:
        return -1
\end{lstlisting}

\newpage

\section{Sunday}

\subsection{Sunday}

Sunday是从前往后匹配的算法，在匹配失败时重点关注的是文本串中参加匹配的最末位字符的下一位字符。如果该字符没有在模式串中出现则直接跳过，移动位数为模式串长度 + 1，否则移动位数为模式串长度 - 该字符最右出现的下标。\\

Sunday算法巧妙的地方在于它发现匹配失败之后可以直接考察文本串中参加匹配的最末尾字符的下一个字符。\\

例如当文本串S = "bcaitsnaxzfinihao"，P = "nihao"。\\

S[0]为b，P[0]为n，匹配失败。关注文本串中参加匹配的最末位字符的下一位字符s，该字符并没在模式串中出现，因此将模式串向右移动模式串长度 + 1，即5 + 1 = 6。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}         & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5}          & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} \\
			\hline
			\textcolor{red}{b} & c          & a          & i          & t          & \textcolor{blue}{s} & n          & a          & x          & z          & f           & i           & n           & i           & h           & a           & o           \\
			\hline
			\textcolor{red}{n} & i          & h          & a          & o          &                     &            &            &            &            &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

S[7]为a，P[1]为i，匹配失败。关注文本串中参加匹配的最末位字符的下一位字符i，该字符在模式串中最右出现出现下标为1，因此将模式串向右移动模式串长度 - 最右下标，即5 - 1 = 4。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6}         & \textbf{7}         & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11}         & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} \\
			\hline
			b          & c          & a          & i          & t          & s          & \textcolor{red}{n} & \textcolor{red}{a} & x          & z          & f           & \textcolor{blue}{i} & n           & i           & h           & a           & o           \\
			\hline
			           &            &            &            &            &            & \textcolor{red}{n} & \textcolor{red}{i} & h          & a          & o           &                     &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11}         & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} \\
			\hline
			b          & c          & a          & i          & t          & s          & n          & a          & x          & z          & f           & \textcolor{blue}{i} & n           & i           & h           & a           & o           \\
			\hline
			           &            &            &            &            &            &            &            &            &            & n           & \textcolor{blue}{i} & h           & a           & o           &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

S[10]为f，P[0]为n，匹配失败。关注文本串中参加匹配的最末位字符的下一位字符a，该字符在模式串中最右出现出现下标为3，因此将模式串向右移动模式串长度 - 最右下标，即5 - 3 = 2。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10}        & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15}         & \textbf{16} \\
			\hline
			b          & c          & a          & i          & t          & s          & n          & a          & x          & z          & \textcolor{red}{f} & i           & n           & i           & h           & \textcolor{blue}{a} & o           \\
			\hline
			           &            &            &            &            &            &            &            &            &            & \textcolor{red}{n} & i           & h           & a           & o           &                     &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15}         & \textbf{16} \\
			\hline
			b          & c          & a          & i          & t          & s          & n          & a          & x          & z          & f           & i           & n           & i           & h           & \textcolor{blue}{a} & o           \\
			\hline
			           &            &            &            &            &            &            &            &            &            &             &             & n           & i           & h           & \textcolor{blue}{a} & o           \\
			\hline
		\end{tabular}
	}
\end{table}

此时，模式串匹配成功。\\

\mybox{Sunday}

\begin{lstlisting}[language=Python]
def sunday(s, p):
    i = 0
    j = 0
    result = 0
    
    while i < len(s) and j < len(p):
        if s[i] == p[j]:
            i += 1
            j += 1
            continue

        idx = result + len(p)
        if idx >= len(s):
            return -1

        k = len(p) - 1
        while k >= 0 and s[idx] != p[k]:
            k -= 1

        i = result
        i += len(p) - k
        result = i
        j = 0

        if result + len(p) > len(s):
            return -1

    return result
\end{lstlisting}

\newpage

\section{BM}

\subsection{BM（Boyer-Moore）}

BM算法的名字取自于它的两位发明者，计算机科学家Bob Boyer和J Strother Moore。为了能减少比较，BM算法制定了两条规则：

\begin{itemize}
	\item 坏字符规则（bad character）
	\item 好后缀规则（good suffix）
\end{itemize}

\vspace{0.5cm}

\subsection{坏字符规则}

坏字符是指文本串与模式串不匹配的字符。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8}         & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & \textcolor{red}{T} & G          & G           & T           & A           & G           & C           & G           & G           & C           & G           & A           & A           \\
			\hline
			G          & T          & A          & G          & C          & G          & G          & C          & \textcolor{red}{G} &            &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

咦？为什么坏字符不是主串中下标为2的字符T呢？那个位置不是先被检测的到吗？\\

BM算法的检测顺序是从字符串的最右侧向最左侧进行的。当检测到第一个坏字符后，并没有必要让模式串一位一位向后挪动并比较。因为只有模式串与坏字符对齐的位置相同的情况下，两者才有匹配的可能。由于模式串的第1位字符也是T，这样就可以直接把模式串中的T与文本串的坏字符对齐，进行下一轮比较。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8}          & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & \textcolor{blue}{T} & G          & G           & T           & A           & G           & C           & G           & G           & C           & G           & A           & A           \\
			\hline
			           &            &            &            &            &            &            & G          & \textcolor{blue}{T} & A          & G           & C           & G           & G           & C           & G           &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

坏字符的位置越靠右，下一轮模式串的挪动跨度就可能越长，节省的比较次数也就越多。这就是BM算法从右向左检测的好处。\\

接着，从右向左成功匹配GCG，并遇到坏字符A。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9}          & \textbf{10} & \textbf{11} & \textbf{12}         & \textbf{13}        & \textbf{14}        & \textbf{15}        & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & T          & G                   & G           & T           & \textcolor{blue}{A} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} & G           & C           & G           & A           & A           \\
			\hline
			           &            &            &            &            &            &            & G          & T          & \textcolor{blue}{A} & G           & C           & \textcolor{red}{G}  & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

按照类似的方式，找到模式串的第2位字符A，将它与文本串的坏字符对齐。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10}        & \textbf{11}        & \textbf{12}        & \textbf{13}        & \textbf{14}        & \textbf{15}        & \textbf{16}        & \textbf{17}        & \textbf{18}        & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & T          & G          & \textcolor{red}{G} & \textcolor{red}{T} & \textcolor{red}{A} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} & A           & A           \\
			\hline
			           &            &            &            &            &            &            &            &            &            & \textcolor{red}{G} & \textcolor{red}{T} & \textcolor{red}{A} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

如果出现坏字符在模式串中不存在的情况，就直接把模式串挪到主串坏字符的下一位。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8}         & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & \textcolor{red}{T} & G          & G           & T           & A           & G           & C           & G           & G           & C           & G           & A           & A           \\
			\hline
			G          & C          & A          & I          & C          & G          & G          & C          & \textcolor{red}{G} &            &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8}         & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & T          & A          & T          & A          & G          & C          & \textcolor{red}{T} & G          & G           & T           & A           & G           & C           & G           & G           & C           & G           & A           & A           \\
			\hline
			           &            &            &            &            &            &            &            &                    & G          & C           & A           & I           & C           & G           & G           & C           & G           &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

\vspace{0.5cm}

\subsection{好后缀规则}

好后缀是指文本串与模式串当中相匹配的后缀。\\

例如对于这个例子，如果继续使用坏字符规则，模式串只能向后挪动一位。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2}          & \textbf{3}          & \textbf{4}         & \textbf{5}         & \textbf{6}         & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} \\
			\hline
			C          & T          & G                   & \textcolor{blue}{G} & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} & A          & G          & C          & G           & G           & A           & A           \\
			\hline
			G          & C          & \textcolor{blue}{G} & \textcolor{red}{A}  & \textcolor{red}{G} & \textcolor{red}{C} & \textcolor{red}{G} &            &            &            &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

为了能真正减少比较次数，就需要使用好后缀规则。在第一轮比较中，文本串和模式串都有共同的后缀GCG，这就是所谓的好后缀。如果模式串的其它位置也包含与GCG相同的子串，那么就可以挪动模式串，让这个子串与好后缀对齐。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}          & \textbf{1}          & \textbf{2}          & \textbf{3} & \textbf{4}          & \textbf{5}          & \textbf{6}          & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} \\
			\hline
			C                   & T                   & G                   & G          & \textcolor{blue}{G} & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G           & G           & A           & A           \\
			\hline
			\textcolor{blue}{G} & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & \textcolor{red}{G}  & \textcolor{red}{C}  & \textcolor{red}{G}  &            &            &            &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}          & \textbf{5}          & \textbf{6}          & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} \\
			\hline
			C          & T          & G          & G          & \textcolor{blue}{G} & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G           & G           & A           & A           \\
			\hline
			           &            &            &            & \textcolor{blue}{G} & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G           &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

如果模式串中不存在其它与好后缀相同的片段，是不是可以直接把模式串挪到好后缀之后？\\

使不得！这里还要判断一种特殊情况，模式串的前缀是否和好后缀的后缀相匹配，免得挪过头了。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}          & \textbf{1}          & \textbf{2} & \textbf{3} & \textbf{4}          & \textbf{5}          & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} \\
			\hline
			T                   & G                   & G          & G          & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G          & G           & A           & A           \\
			\hline
			\textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C                   & G                   &            &            &            &            &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{2.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}          & \textbf{5}          & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} \\
			\hline
			T          & G          & G          & G          & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G          & G           & A           & A           \\
			\hline
			           &            &            &            & \textcolor{blue}{C} & \textcolor{blue}{G} & A          & G          & C          & G          &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

那应该什么时候用坏字符规则，什么时候用好后缀规则呢？\\

可以在每一轮字符比较之后，按照坏字符和好后缀规则分别计算相应的挪动距离，哪一种距离更长，就把模式串挪动对应的长度。比如坏字符可以让模式串在下一轮挪动3位，好后缀可以让模式串移动5位，那么就应该采用好后缀规则。

\newpage

\section{KMP}

\subsection{KMP（Knuth-Morris-Pratt）}

KMP算法是一个里程碑似的算法，它的出现宣告了人类找到了线性时间复杂度的字符串匹配算法。在此之后才出现了其它线性时间的字符串匹配算法，比如BM算法和Sunday算法。\\

KMP算法由三位计算机科学家D. E. Knuth、J. H. Morris和V. R. Pratt提出，KMP这个算法名字正是取自这三个人的姓氏首字母。\\

与BM算法类似，KMP算法也在试图减少无谓的字符比较，但KMP算法把专注点放在了已匹配的前缀。\\

在每一次匹配过程中，其实可以判断出后续几次匹配是否会成功。算法的核心就是每次匹配过程中推断出后续完全不可能匹配成功的部分，从而减少比较的次数。\\

例如主串中已匹配末尾的GTG是最长可匹配后缀，模式串中开头的GTG是最长可匹配前缀。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}          & \textbf{1}          & \textbf{2}          & \textbf{3}          & \textbf{4}          & \textbf{5}         & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G                   & T                   & \textcolor{blue}{G} & \textcolor{blue}{T} & \textcolor{blue}{G} & \textcolor{red}{A} & G          & C          & T          & G          & G           & T           & G           & T           & G           & T           & G           & C           & F           & A           & A           \\
			\hline
			\textcolor{blue}{G} & \textcolor{blue}{T} & \textcolor{blue}{G} & T                   & G                   & \textcolor{red}{C} & F          &            &            &            &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

将最长可匹配后缀与最长可匹配前缀对齐。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2}          & \textbf{3}          & \textbf{4}          & \textbf{5}         & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & \textcolor{blue}{G} & \textcolor{blue}{T} & \textcolor{blue}{G} & \textcolor{red}{A} & G          & C          & T          & G          & G           & T           & G           & T           & G           & T           & G           & C           & F           & A           & A           \\
			\hline
			           &            & \textcolor{blue}{G} & \textcolor{blue}{T} & \textcolor{blue}{G} & \textcolor{red}{T} & G          & C          & F          &            &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

主串中已匹配末尾的G是最长可匹配后缀，模式串中开头的G是最长可匹配前缀。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2}          & \textbf{3} & \textbf{4}          & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & G                   & T          & \textcolor{blue}{G} & A          & G          & C          & T          & G          & G           & T           & G           & T           & G           & T           & G           & C           & F           & A           & A           \\
			\hline
			           &            & \textcolor{blue}{G} & T          & G                   & T          & G          & C          & F          &            &             &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

将最长可匹配后缀与最长可匹配前缀对齐。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{1.5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4}          & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} & \textbf{12} & \textbf{13} & \textbf{14} & \textbf{15} & \textbf{16} & \textbf{17} & \textbf{18} & \textbf{19} & \textbf{20} \\
			\hline
			G          & T          & G          & T          & \textcolor{blue}{G} & A          & G          & C          & T          & G          & G           & T           & G           & T           & G           & T           & G           & C           & F           & A           & A           \\
			\hline
			           &            &            &            & \textcolor{blue}{G} & T          & G          & T          & G          & C          & F           &             &             &             &             &             &             &             &             &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

KMP算法的整体思路就是在已匹配的前缀当中寻找最长可匹配后缀子串和最长可匹配前缀子串，在下一轮直接把两者对齐，从而实现模式串的快速移动。\\

那么如何找到一个字符串前缀的最长可匹配后缀子串和最长可匹配前缀子串呢？难道在每一轮都要重新遍历吗？\\

要找到这两个子串没有必要每次都去遍历，可以事先缓存到一个集合当中，用的时候再去集合里面取。这个集合被称为next数组，如何生成next数组是KMP算法的最大难点。\\

\subsection{next数组}

next数组实质上就是找出模式串前后字符重复出现的个数，next[i]表示模式串T[0]到T[i]这个子串使得前k个字符等于后k个字符的最大值，其中k不能取i + 1，因为子串一共才i + 1个字符，自己跟自己相等毫无意义。\\

例如当文本串S = "ABABAABAABAC"，P = "ABAABAC"。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{5mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{模式串}   & \textbf{A} & \textbf{B} & \textbf{A} & \textbf{A} & \textbf{B} & \textbf{A} & \textbf{C} \\
			\hline
			\textbf{next数组} & 0          & 0          & 1          & 1          & 2          & 3          & 0          \\
			\hline
		\end{tabular}
	}
	\caption{模式串ABAABAC的next数组}
\end{table}

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0}          & \textbf{1}          & \textbf{2}          & \textbf{3}         & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \textbf{8} & \textbf{9} & \textbf{10} & \textbf{11} \\
			\hline
			\textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{red}{B} & A          & A          & B          & A          & A          & B          & A           & C           \\
			\hline
			\textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{red}{A} & B          & A          & C          &            &            &            &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

已经成功匹配3个，查看next[3-1] = 1，表示最长匹配前后缀长度为1。模式串需要跳过的长度为匹配上的长度减去最长匹配前后缀长度，即3 - 1 = 2。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2}          & \textbf{3}          & \textbf{4}          & \textbf{5}          & \textbf{6}          & \textbf{7}          & \textbf{8}         & \textbf{9} & \textbf{10} & \textbf{11} \\
			\hline
			A          & B          & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{red}{A} & B          & A           & C           \\
			\hline
			           &            & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{red}{C} &            &             &             \\
			\hline
		\end{tabular}
	}
\end{table}

已经成功匹配6个，查看next[6-1] = 3，表示最长匹配前后缀长度为3。模式串需要跳过的长度为匹配上的长度减去最长匹配前后缀长度，即6 - 3 = 3。

\begin{table}[H]
	\centering
	\setlength{\tabcolsep}{3mm}{
		\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|}
			\hline
			\textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5}          & \textbf{6}          & \textbf{7}          & \textbf{8}          & \textbf{9}          & \textbf{10}         & \textbf{11}         \\
			\hline
			A          & B          & A          & B          & A          & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{C} \\
			\hline
			           &            &            &            &            & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{A} & \textcolor{blue}{B} & \textcolor{blue}{A} & \textcolor{blue}{C} \\
			\hline
		\end{tabular}
	}
\end{table}

在跳过不可能匹配的趟数后，并非再从头开始匹配，而是从之前不匹配的位置开始。\\

\subsection{算法分析}

假设模式串的长度为m，主串的长度为n。KMP算法唯一的额外空间是next数组，那么空间复杂度就是$ O(m) $。\\

至于时间复杂度，KMP算法包括两步。第一步生成next数组，时间复杂度为$ O(m) $；第二步是对主串的遍历，时间复杂度为$ O(n) $。因此KMP算法的整体时间复杂度就是$ O(m + n) $。\\

\mybox{KMP}

\begin{lstlisting}[language=Python]
def get_nexts(p):
    next = [0] * len(p)
    j = 0
    
    for i in range(2, len(p)):
        while j != 0 and p[j] != p[i-1]:
            j = next[j]
        if p[j] == p[i-1]:
            j += 1
        next[i] = j
    return next

def kmp(s, p):
    next = get_nexts(p)
    j = 0
    for i in range(len(s)):
        while j > 0 and s[i] != p[j]:
            j = next[j]
        if s[i] == p[j]:
            j += 1
        if j == len(p):
            return i - len(p) + 1
    return -1
\end{lstlisting}

\newpage